--带权重的 A-ExpJ 算法蓄水池抽样
tablex = function(t)
    if not t then
        return "nil"
    end

	if type(t)~="table" then
		return tostring(t)
	end

	local function ser_table(tbl)
		local tmp = {}
		for k,v in pairs(tbl) do
			local key = type(k)=="number" and "["..k.."]" or k
			local tp = type(v)
			if tp=="table" then
				table.insert(tmp, key.."="..ser_table(v))
			else
				if tp == "string" then
					table.insert(tmp, key.."="..string.format("%q",v))
				elseif tp=="boolean" then
					table.insert(tmp, key.."="..tostring(v))
                elseif tp=="function" then
                    --函数不打印
				else
					table.insert(tmp, key.."="..v)
				end
			end
		end
		return "{"..table.concat(tmp,",").."}"
	end

	return ser_table(t)
end

binary_search2 = function(rank, rand_score)
    assert( rank ~= {})
    -- local len = #rank
    -- assert( len > 0)
    table.sort(rank, function(a, b)
        return a < b
    end)
    local left = 1
    local right = #rank
    while(left <= right) do
        local mid = math.ceil(right + (left - right) / 2)

        print("mid is".." "..mid)
        if rand_score == rank[mid] then
            return mid
        elseif rand_score > rank[mid] then
            left = mid + 1
        elseif rand_score < rank[mid] then
            right = mid - 1
        end
    end
    return -1
end

binary_search = function(rank, rand_score)
    assert( rank ~= {})
    -- local len = #rank
    -- assert( len > 0)
    table.sort(rank, function(a, b)
        return a.score < b.score
    end)
    local left = 1
    local right = #rank
    print("----2----"..right)
    while(left <= right) do
        local mid = math.ceil(right + (left - right) / 2)

        print("mid is".." "..mid)
        if rand_score == rank[mid].score then
            return mid
        elseif rand_score > rank[mid].score then
            left = mid + 1
        elseif rand_score < rank[mid].score then
            right = mid - 1
        end
    end
    return -1
end

aexpj_weight_sampling = function(data_array, weight_array, n, m)
    local result, rank = {}, {}
    for i = 1, m do
        local rand_score = math.ceil(math.random() ^ (1 / weight_array[i]))
        print("---3---"..rand_score)
        local idx = binary_search(rank, rand_score)
        if idx < 0 then
            print("---1---")
            idx = 1
        end
        print(string.format("idx is:".." "..idx))
        table.insert(rank, idx, {score = rand_score, data = data_array[i]})
        print("---4---", tablex(rank))
    end

    local weight_sum, xw = 0, math.log(math.random()) / math.log(rank[m].score)

    print('----6----'..xw)
    for i = m + 1, n do
        weight_sum = weight_sum + weight_array[i]
        print('----5----'..weight_sum)
        if weight_sum >= xw then
            local tw = rank[m].score ^ weight_array[i]
            local rand_score = (math.random() * (1 - tw) + tw) ^ (1 / weight_array[i])
            local idx = binary_search(rank, rand_score)
            table.insert(rank, idx, {score = rand_score, data = data_array[i]})
            table.remove(rank)
            weight_sum = 0
            xw = math.log(math.random()) / math.log(rank[m].score)
        end
    end

    for i = 1, m do
        result[i] = rank[i].data
    end

    return result
end

--for test
-- local rank = {1,9,3,6,5,4,7,8,2,10}
-- print(tablex(rank))
-- local rank_score = 9
-- local t = binary_search(rank, rank_score)

-- print(t)
local data_array = {10, 20, 50, 20}
local weight_array = {30, 20, 40, 10}
local n = 4
local m = 2

local t = aexpj_weight_sampling(data_array, weight_array, n, m)

print(tablex(t))